\begin{appendix}
\section{Provable Algorithm Pseudocodes}
\label{sec:provablealgos}

%\subsection{Single-skill Density Objective}
%\label{sec:s-DensestAlkAlgo}
%\begin{algorithm}[]
%\caption{s-DensestAlk($G, {\cal T}$)}
%\label{algo:sDlk}
%\begin{algorithmic}[1]
%\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
%\WHILE{ $|D_i \cap S(a)| < k$ where ${\cal T} = \{<a, k>\}$}
%\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
%\STATE $D_{i + 1} \leftarrow union(D_i, H_{i + 1})$
%\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
%\STATE $i \leftarrow i + 1$
%\ENDWHILE
%\FOR {$each \ D_i$}
%\STATE $n_a =$ number of nodes of skill $a$ in $D_i$
%\STATE Add $max(k - n_a, 0)$ nodes of skill $a$ to $D_i$ to form $D'_i$
%\ENDFOR
%\STATE Return $D'_i$ which has the maximum density
%\end{algorithmic}
%\end{algorithm}

\subsection{Multi-skill Density Objective}
\label{sec:m-DensestAlkAlgo}
\begin{algorithm}[H]
\caption{m-DensestAlk($G, {\cal T}$)}
\label{algo:mDlk}
\begin{algorithmic}[1]
\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
\WHILE{ $|D_i \cap S(a_j)| < k_j$ for any $<a_j, k_j> \in {\cal T}$}
\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
\STATE $D_{i + 1} \leftarrow union(D_i, H_{i + 1})$
\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
\STATE $i \leftarrow i + 1$
\ENDWHILE
\FOR {$each \ D_i$}
\STATE $D'_i \leftarrow D_i$
\FOR {$each \ <a_1, k_1> \in {\cal T}$}
\STATE $n_{aj} =$ number of nodes of skill $a_j$ in $D_i$
\STATE Add $max(k_j - n_{aj}, 0)$ nodes of skill $a_j$ to $D'_i$
\ENDFOR
\ENDFOR
\STATE Return $D'_i$ which has the maximum density
\end{algorithmic}
\end{algorithm}

\subsection{Diameter Objective}
\label{sec:minDiaAlgo}
\begin{algorithm}[H]\label{algo:minDia}
\caption{MinDiameter(G, {\cal T})} 
\label{algo:minDia}
\begin{algorithmic}[1]
\FOR{each $<a, k> \in T$}
\STATE $S(a) = \{ i \mid a \in X_i \}$
\ENDFOR
\STATE $a_{rare} = \arg \min_{<a, k>\ \in T} |S(a)|$
\FOR{each $i \in S(a_{rare})$}
\FOR{each $<a, k>\ \in T$}
\STATE $R_{ia} = d_k(i, S(a), k)$
\ENDFOR
\STATE $R_i \leftarrow \max_a R_{ia}$
\ENDFOR
\STATE $i^* \leftarrow \arg \min R_i$
\STATE ${\cal X'} = \{ i^* \}$
\FOR{each $<a, k>\ \in T$}
\STATE ${\cal X'} = {\cal X'} \cup \{  Path_k(i^*, S(a), k) \}$
\ENDFOR
\end{algorithmic}
\end{algorithm}

\section{Hardness of Density Objective}
\label{sec:densityNPProof}
\begin{proof} [of Theorem~\ref{thm:densityhardness}]
We prove the $claim$ by a reduction from the {\it Densest at least $k$ subgraph (DalkS)} problem defined in ~\cite{KS}. An instance of {\it DalkS} consists of a graph $G({\cal X}, E)$, and a constant $k$, and the solution is a maximum density subgraph with at least $k$ nodes. We transform it into an instance of {\it Density-sTF} problem by defining a skill $a$ for every node $v \in V$ in which case a solution would be a maximum density subgraph with at least $k$ nodes that have skill $a$. And since skill $a$ is defined for every node in $G$, it is easy to see that ${\cal X'} \subseteq {\cal X} $ is the solution to the problem {\it Density-sTF}  iff it is a solution to the problem {\it DalkS}. The problem {\it Density-sTF} is a special case of {\it Density-mTF} which implies that {\it Density-mTF} is NP-hard. 
\end{proof}

\section{Figures and Proofs for Single-skill Density Approximation}
\subsection{Naive extension of DensestAtleastK}
\label{subsec:4approx}
\begin{claim}
Adding at most $k$ skilled nodes to the solution subgraph returned by the algorithm  DensestAtleastK ~\cite{KS} achieves $4$-approximation to the problem Density-sTF.
\end{claim}
\begin{proof}
Let $G(V, E)$ be the input graph, and let $S(a) \subseteq V$ denote the nodes with the skill $a$. Run the algorithm {\it DensestAtleastK} on $G$ to find the maximum density subgraph that contains at least $k$ nodes. Let $\cal X$ denote the maximum density solution subgraph returned by {\it DensestAtleastK} and ${H_k}^*$ denote the optimal solution subgraph. Let, $n_a = |V({\cal X}) \cap S(a)|$ denote the number of nodes in $\cal X$ with skill $a$. Now, construct a subgraph, say $\cal X'$ by adding $\max (0, k - n_a)$ nodes to $\cal X$. Let $H^*$ denote the optimal solution subgraph to the problem {\it Density-sTF}. By definition, it is obvious that the density of subgraph $H^*$ is at most the density of ${H_k}^*$. Let $d', d, {d_k}^*$ and $d^*$ denote the density of the subgraphs ${\cal X', X}, {H_k}^*$ and $H^*$ respectively.  \\
Since the algorithm {\it DensestAtleastK}  guarantees a 2-approximation to the problem of finding the maximum density subgraph of size at least $k$ nodes,\\
$d \ge \frac{{d_k}^*}{2} \ge \frac{d^*}{2}$ \\
Further,\\
$d' = \frac{W({\cal X'})}{|V({\cal X'})|} \ge \frac{W({\cal X})}{|V({\cal X})| + k} \ge \frac{W({\cal X})}{2 |V({\cal X})|} =  \frac{d}{2}$ ($|V({\cal X})| \ge k$) \\
$\ge \frac{d^*}{4}$\\
This proves the claim.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:densityapprox} Cont.}
\label{sec:3approxProof}
%\begin{proof} [of Theorem~\ref{thm:densityapprox}]
%\setcounter{equation}{0}
%Let $H^*$ denote an optimal solution and $d^* =  \frac{W(H^*)}{|V(H^*)|}$ denote density of the optimal solution. 
%
%If the number of iterations is 1, then $H_1$ is the maximum density subgraph that contains at least $k$ nodes of skill $a$. Therefore, $H^* = H_1$ and the algorithm returns it. Otherwise, say the algorithm iterates for $l \ge 2$ rounds. There can be two cases:
%
%\noindent {\bf Case 1:} There exists an $l' < l$ such that \\
%$W(D_{l' - 1} \cap H^*) < \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.25, bb = 30 300 500 700]{3_approx_dia_1.eps}
\caption{$D_{l'} = D_{i1} \cup D_{i2} \cup X$}\label{fig:3approx}
\end{center}
\end{figure}

%\noindent {\bf Case 2:} There exists no such $l' < l$.
%
%Before analyzing the two cases in detail, note that by construction
%$density(H_i) \le density(D_i) \le density(D_{i - 1})$. We now consider case 2 first and later case $1$.

%\noindent {\bf Proof for Case 2.} 

%Since the algorithm terminates after $l$ iterations, $D_l$ contains at least $k$ nodes of skill $a$. Further, we know that for each $j \le l - 1, W(D_j \cap  H^*)  < \frac{W(H^*)}{2}$ \\ 
%$\Rightarrow W(G_j \cap  H^*)  \ge \frac{W(H^*)}{2}$ \\ 
%$\Rightarrow \frac{W(G_j \cap H^*)}{|V(G_j \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|}$ \\ 
%$\Rightarrow G_j$ contains a subgraph of density $\ge \frac{d^*}{2}$ \\ 
%$\Rightarrow density(H_l) \ge \frac{d^*}{2}$ \\ 
%$\Rightarrow density(D_l) \ge \frac{d^*}{2}$

%Thus, $D_l$ has density $\ge \frac{d^*}{2}$ and contains at least $k$ nodes of skill $a$. Therefore, the algorithm indeed returns a subgraph of density at least $\ge \frac{d^*}{2}$.

%\noindent{\bf Proof of Case 1(b).}
%According to step $10$, the algorithm adds at most $\frac{|V(H^*)|}{2}$ nodes to $D_{l'}$ to form $D'_{l'}$ with density, say $d$.
%\begin{enumerate}[i]
%\squishlist
%\item $|V(D_{l'})| \ge |V(H^*)|$ \\
%$d \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(D_{l'})|}{2}}  \ge \frac{d^*}{3}$ 

%\item $|V(D_{l'})| < |V(H^*)|$ \\
%$d \ge \frac{W(D_{l'})}{|V(D_{l'}|) + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(H^*)| + \frac{|V(H^*)|}{2}} \ge  \frac{\frac{W(H^*)}{2}}{\frac{3}{2}|V(H^*)|} \ge \frac{d^*}{3}$
%\squishend
%\end{enumerate} 

\noindent{\bf Proofs of Claims used in Case 1(c).}

%\noindent{\bf Proof for Case 1}
%
%\noindent $W(D_{l' - 1} \cap H^*) < \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$\\
%$\Rightarrow W(G_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$ where $G_{l'} = shrink(G, D_{l' -1})$ \\ 
%$\Rightarrow \frac{W(G_{l'} \cap H^*)}{|V(G_{l'} \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|} = \frac{d^*}{2}$ \\ 
%$\Rightarrow G_{l'}$ has a subgraph of density $\ge \frac{d^*}{2}$ \\ 
%$\Rightarrow density(H_{l'}) \ge \frac{d^*}{2}$  ($H_{l'}  \mbox { is densest subgraph of } G$) \\ 
%$\Rightarrow density(D_{l'}) \ge \frac{d^*}{2}$

%Now, let us divide {\bf Case 1} into following $4$ parts 
%\begin{enumerate}[(a)]
%\item $|V(D_{l'})| \le  \frac{k}{2}$ \\
%According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$ to obtain the subgraph, say $D$, with density $d$\\
%$d \ge \frac{W(D_{l'})}{|V(D_{l'})| + k} \ge \frac{\frac{W(H^*)}{2}}{\frac{k}{2} + k} \ge \frac{\frac{W(H^*)}{2}}{\frac{3 |V(H^*)|}{2}} = \frac{d^*}{3}$ 
%
%\item $|V(D_{l'})| \ge  2k $
%
%According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$. Further, we know that $density(D_{l'}) \ge \frac{d^*}{2}$ therefore, the resulting subgraph, $D'_{l'}$ has density 
%
%\noindent $d = \frac{W(D_{l'})}{|V(D_{l'})| + k} \ge \frac{W(D_{l'})}{\frac{3}{2} |V(D_{l'})|}  \ge  \frac{d^*}{3}$
%
%\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $ |V(D_{l'}) \cap V(H^*)| \ge \frac{|V(H^*)|}{2}$
%
%According to step $10$, algorithm adds at most $\frac{|V(H^*)|}{2}$ nodes to $D_{l'}$ to form $D'_{l'}$ with density, say $d$.
%
%\begin{enumerate}[i]
%\item $|V(D_{l'})| \ge |V(H^*)|$ \\
%$d \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(D_{l'})|}{2}}  \ge \frac{d^*}{3}$ 
%
%\item $|V(D_{l'})| < |V(H^*)|$ \\
%$d \ge \frac{W(D_{l'})}{|V(D_{l'}|) + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(H^*)| + \frac{|V(H^*)|}{2}} \ge  \frac{\frac{W(H^*)}{2}}{\frac{3}{2}|V(H^*)|} \ge \frac{d^*}{3}$
%\end{enumerate} 
%
%\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $|V(D_{l'}) \cap V(H^*)| < \frac{|V(H^*)|}{2}$
%
%If $d_{l'} = density(D_{l'}) \ge d^*$, then adding at most $k$ vertices gives a subgraph $D'_{l'}$ with density, say $d$ such that
%
%\noindent $d = \frac{W(D_{l'})}{ |V(D_{l'})| + k} \ge \frac{W(D_{l'})}{|V(D_{l'})| + 2 |V(D_{l'})|}  \ge \frac{W(D_{l'})}{3 |V(D_{l'})|} \ge \frac{d^*}{3}$
%
%Therefore, $D_{l'}$ is a subgraph that contains at least $k$ nodes of skill $a$ and has density $d \ge \frac{d^*}{3}$. We are done here.
%
%Now, assume that $d_{l'} < d^*$.
%
%In the rest of the proof, we divide $D_{l'}$ into subgraphs as explained below and shown in Figure~\ref{fig:3approx}. 
%
%$\mbox{Let } G' = D_{l'} \cap H^* $. 
%
%\begin{claim}
%\label{claim:case2Claim1}$W(G')\ge \frac{W(H^*)}{2}$ and $density(G')\ge d^*$.
%\end{claim}
\begin{proof} [of Claim~\ref{claim:case2Claim1}]
$|V(G')| = |V(D_{l'} \cap H^*)| < \frac{|V(H^*)|}{2} $ and $W(G') = W(D_{l'} \cap H^*) \ge  \frac{W(H^*)}{2} $. \\
$\Rightarrow density(G') \ge \frac{\frac{W(H^*)}{2}}{\frac{|V(H^*)|}{2}} \ge d^* $.
\end{proof}
%
%Define $i$ such that $density(H_i)\ge d^*$ and $density(H_{i+1}) < d^*$. Such an $i\le l'$ exists due to {\sc Claim ~\ref{claim:case2Claim1}} and since $d_{l'} < d^*$.\\ 
%
%$\Rightarrow density(D_i)  = d_i \ge d^*$. 
%
%Let, $n_i = |V(D_i)| $. We now consider two sub-cases. 
%
%\begin{enumerate}[i]
%\item $n_i \ge \frac{|V(H^*)|}{2}$: Add at most $k$ vertices to $D_i$ to get a subgraph $D'_i$ with $density(D'_i) = d$, such that  \\
%$d = \frac{W(D_i)}{|V(D_i)| + k} \ge \frac{W(D_i)}{|V(D_i)| + |V(H^*)|} \ge \frac{W(D_i)}{3 |V(D_i)|} \ge \frac{d^*}{3}$. \\ 
%Thus, $D'_i$ is a subgraph containing at least $k$ nodes of skill $a$ and density $d \ge  \frac{d^*}{3}$ and we are done here.
%
%\item $n_i < \frac{|V(H^*)|}{2}$:  
%We know that $density(G') \ge  d^*$, $density(H_i) \ge d^*$ and $density(H_{i+1}) < d^*$.  Therefore, $G' \cap D_i \ne \phi$.
%We now introduce a few definitions and prove claims about them. 
%
%Let, $D_{i1} = D_i \cap G'$, $D_{i2} = shrink(D_i, D_{i1})$, and $G'' = shrink(G', D_{i1})$ (Figure: ~\ref{fig:3approx1}). Further, let $X = shrink(D_{l'}, D_i)$. \\

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.5, bb = 30 300 500 500]{3_approx_dia_2.eps} 
\caption{$D_{i1} = D_i \cap G'$, $D_{i2} = shrink(D_i, D_{i1})$, $G'' = shrink(G', D_{i1})$}\label{fig:3approx1}
\end{center}
\end{figure}

%%CHANGE PREVIOUS FIGURE ALSO AND PLACE $X$ THERE. 
%
%\begin{claim} 
%\label{claim:case2Claim2}$W(D_{i1}) \ge  \frac{|V(H^*)| d^*}{2} - W(G'')$. 
%\end{claim}
\begin{proof} [of Claim~\ref{claim:case2Claim2}]
$W(G') = W(G'') + W(D_{i1})$ since $G'' = shrink(G', D_{i1})$; but $W(G')\ge \frac{W(H^*)}{2}$ (using {\sc Claim ~\ref{claim:case2Claim1}})
\end{proof}
%
%\begin{claim}
%\label{claim:case2Claim3} $density(D_{i2}) > \frac{d^*}{2}$.
%\end{claim}
\begin{proof} [of Claim~\ref{claim:case2Claim3}]
Recall that for each $j \le i, density(H_j) > d^*$. Further, $H_j = \mbox{ densest subgraph of } shrink(G, D_{j-1})$.
Therefore, for each $v\in H_j$, the degree of $v$ induced in $H_j$ is at least $d^*$. Therefore, for all $v\in D_i$, $degree(v) > d^*$ (here we abuse notation to denote $v$'s degree induced in $D_{i}$ by $degree(v)$).
\end{proof}
%
%For convenience, let $n_{x} = |V(X)|$, $n_{l'} = |V(D_{l'})|$, $n_{i1} = |V(D_{i1})|$, $n_{i2} = |V(D_{i2})|$, and $n'' = |V(G'')|$.
%
%\begin{claim}
%\label{claim:case2Claim4}$W(X) - W(G'') \ge \frac{d^*}{2} (n_{x} - n'')$.
%\end{claim}
\begin{proof} [of Claim~\ref{claim:case2Claim4}]
%Notice, $G'' \subseteq X$. 
Since $H_{l'}$ is the maximum density subgraph of $shrink(G, D_{l'-1})$, $density(H_{l'}) \ge density(S)$ for any $S \subseteq H_{l'},$. 
Further, since $X = shrink(D_{l'}, D_i)$, and $G'' = shrink(G', D_i \cap G')$, we have  $G'' \subseteq X$.
Therefore, $density(H_j) \ge density(H_j \cap G'')$ (for all $i < j \le l'$). \\
%Further, $X = H_{i+1} \cup H_{i + 2} \cup \cdot \cdot \cdot H_{l'} \Rightarrow G'' \subseteq X$ \\
Therefore, $W(X) - W(G'') $\\
$= \sum_{j=i+1}^{l'}{W(H_j)} - \sum_{j=i+1}^{l'}{W(H_{j} \cap G'')}$\\
%$= (W(H_{i+1}) + \cdot \cdot \cdot + W(H_{l'}) ) - (W(H_{i + 1} \cap G'') +\cdot \cdot \cdot +  W((H_{l'} \cap G'')$ \\
$\ge \sum_{j=i+1}^{l'}{density(H_{j}) (\mid H_{j} \mid - \mid H_{j} \cap G'' \mid)}$\\
%$\ge density(H_{i + 1}) (\mid H_{i+1} \mid - \mid H_{i + 1} \cap G'' \mid) + \cdot \cdot \cdot + density(H_{l'}) (\mid H_{l'} \mid - \mid H_{l'} \cap G'' \mid) $
$\ge \frac{d^*}{2} (n_x - n'')$.
\end{proof}
%
%Notice that we have (lower) bounded the density or the weight of each of $D_{i1}$, $D_{i2}$, and $X$, the three components that add up to $D_{l'}$. We are now ready to argue about the density of $D_{l'}$ when $k$ vertices are added to it. Before initiating this analysis, we briefly state a claim relating the sizes of these components. 
%
%\begin{claim}
%\label{claim:case2Claim5}$n_{i2} + n_x - n''\ge n_{l'} - \frac{|V(H^*)|}{2}$
%\end{claim}
\begin{proof} [of Claim~\ref{claim:case2Claim5}]
This follows using $|V(G')|  \le \frac{|V(H^*)|}{2}$ and the definition $G'' = shrink(G', D_{i1})$.
\end{proof}
%
%We now complete the analysis. \\  
%
%\noindent $d = density(D) \ge \frac{W(D_{l'})}{n_{l'} + k}$ \\
%$= \frac{W(D_i) + W(X)}{n_{l'} + k} = \frac{W(D_{i1}) + W(D_{i2}) + W(X)}{n_{l'} + k}$ \\ 
%$\ge \frac{\frac{d^* |V(H^*)|}{2} - W(G'') + \frac{d^*n_{i2}}{2} + W(X)}{n_{l'} + k}$ (using {\sc Claim ~\ref{claim:case2Claim2},~\ref{claim:case2Claim3}})\\ 
%$\ge \frac{\frac{d^* |V(H^*)|}{2} + \frac{d^*n_{i2}}{2} + \frac{d^*}{2}(n_x - n'')}{n _{l'}+ k}$ (using {\sc Claim ~\ref{claim:case2Claim4}})\\ 
%$\ge \frac{d^*}{2} \frac{|V(H^*)| + n_{l'} - \frac{|V(H^*)|}{2}}{n_{l'} + k}$ (using {\sc Claim ~\ref{claim:case2Claim5}}) \\ 
%$\ge \frac{d^*}{4} \frac{2n_{l'} + k}{n_{l'} + k} \ge \frac{d^*}{3}$ (since $\frac{k}{2} < n_{l'}$).
%\end{enumerate}
%\end{enumerate} 
%Remark: Cases (c) and (d) do not use the bound $|V(D_{l'})| < 2k$; so they together subsume case (b), but we have presented (b) for clarity.
%\end{proof}

\section{Multi-skill Density Approximation}
\label{sec:multiDensity3Approx}
\begin{proof} [of Theorem~\ref{thm:multidensityapprox}]
Let $m =\ \mid${\cal T}$\mid$ and $k = \sum_{j=1}^{m}{k_j}$ where $k_j$ number of individuals are required of skill $a_j$ s.t. $<a_j,k_j> \in {\cal T}$. Since each node contributes to at most one skill, an optimal solution, $H^*$, has at least $k$ vertices. The proof for {\it m-DensestAlk} is analogous to the proof for {\it s-DensestAlk} with the only difference that instead of adding any $k$ nodes of skill $a$ to $D_i$s, we add $k_j$ nodes of skill $a_j$ s.t. $<a_j,k_j> \in {\cal T}$.
\end{proof}

\section{Hardness of Min Diameter Objective}
% ~\ref{Thm:minDiaNP}}
\label{sec:minDiaNPProof}
\begin{proof} [of Theorem~\ref{Thm:minDiaNP}]
The problems {\it Diameter-sTF} and {\it Diameter-mTF} are in NP because for a given candidate solution, in polynomial time, it can be verified that the skill-set requirement is satisfied. We prove that {\it Diameter-sTF} is NP-hard by reduction from the 3-satisfiability problem.  Consider a 3-SAT instance, say $\Psi = C_1 \wedge C_2 ... \wedge C_m$, where each clause, $C_j = (x \vee y \vee z)$, and $\lbrace x, y, z \rbrace \in U = \lbrace u_1, \neg u_1, u_2, \neg u_2, \cdot \cdot \cdot, u_n, \neg u_n \rbrace$. Let, $C = \lbrace  C_1, C_2, \cdot \cdot \cdot, C_m \rbrace$. Let $N, M$ denote the number of variables and clauses, respectively. We construct an instance of {\it Diameter-sTF} problem corresponding to the 3-SAT instance $\Psi$ using the following rules.

{\it Rule $1$} For each variable $x$, create two nodes $x, \neg x$ in $G$ and set $w(x, \neg x) = r'$.

{\it Rule $2$} For each clause $C_j$, create two nodes, $C_{j1}$ and $C_{j2}$ in $G$ and set $w(C_{j1}, C_{j2}) = r'$. 

{\it Rule $3$} Pick any $r$ such that $r < r'$. For each pair of variables ($x, y$) where $y \ne \neg x$, set $w(x, y) = r$. Similarly, for each pair of clauses ($C_f, C_g$), where $w(C_f, C_g)$ is not set by rule $2$, set $w(C_f, C_g) = r$.

{\it Rule $4$} 
For each clause, $C_j = (x \vee y \vee z)$, set 

$w(C_{j1}, x) = w(C_{j1}, y) = w(C_{j1}, z) = \frac{r}{2}$ and 

$w(C_{j2}, x) = w(C_{j2}, y) = w(C_{j2}, z) = \frac{r}{2}$ and 

$w(C_{j1}, u) = w(C_{j2}, u) = r$ for each $u \in U - \{x, y, z\}$ 

{\it Rule $5$} For each $u_i, \neg u_i \in U$, associate a skill $a$ to node $u_i, \neg u_i$. And for each $C_j \in C$, associate a skill $a$ to the nodes $C_{j1}, C_{j2}$. 

\begin{claim}
\label{claim:minDiaClaim1} In $G$, $d(x, \neg x) > r$ where $x, \neg x \in U$.
\end{claim}
\begin{proof}
In $G$, for each variable $y (\ne x \ne \neg x), \ d(x, y) = d(\neg x, y) = r$ and $w(x, \neg x) = r' > r$ (rule $1, 3$). Further, both $x$ and $\neg x$ cannot appear together in any clause $C_j \in C$ (pre-processing). Therefore, in $G,\ d(C_{j1}, x) = d(C_{j2}, x) = \frac{r}{2}$ and $d(C_{j1}, \neg x) = d(C_{j2}, \neg x) = r$ (rule $3, 4$). \\
$\Rightarrow d(x, \neg x) > r$
\end{proof}
\begin{claim}
\label{claim:minDiaClaim2} Let $X$ be the subgraph of $G$ and $V(X)$ denote the nodes in $X$. Let $C_{j1}, C_{j2} \in V(X)$ where $C_j = (x \vee y \vee z)$. Then, in $X$, $d(C_{j1}, C_{j2}) = r$ iff $V(X) \cap \{x, y ,z\} \ne \phi$.
\end{claim}
\begin{proof}
Assume $V(X) \cap \{x, y, z\} = \phi$. \\
In $G$, for each clause $C_f (\ne C_{j1} \ne C_{j2}), \ d(C_{j1}, C_f) = d(C_{j2}, C_f) = r$ and $w(C_{j1}, C_{j2}) = r' > r$ (rule $2, 3$). Further, for each $u \in U - \{x, y , z\},\ d(C_{j1}, u) = d(C_{j2}, u) = r$ (rule $4$). Therefore, in $X,  d(C_{j1}, C_{j2}) > r$. However, this is a contradiction because, in $X, d(C_{j1}, C_{j2}) = r$. \\
$\Rightarrow V(X) \cap \{x, y ,z\} \ne \phi$.
\end{proof}
\begin{claim}
\label{claim:minDiaClaim3} Let  $k = N + 2M$. If $\Psi$ has a satisfying assignment then $G$ has a sub-graph $\cal X'$ with $|{\cal X'} \cap S(a)| \ge k$ and $diameter({\cal X'}) \le r$. 
\end{claim}
\begin{proof}
If $\Psi$ has a satisfying assignment, then $G$ has a subgraph $\cal X'$ such that $\cal X'$ contains $C_{j1}, C_{j2}$ for each clause $C_j \in C$, and $u (or \ \neg u) \in U$ if $u (or \  \neg u)$ is set to $1$ in the satisfying assignment for $\Psi$. Note that in the satisfying assignment for $\Psi$ either $u$ or $\neg u$ appears in the assignment. Thus, $\cal X'$ contains exactly $N$ variables and twice the number of clauses. Thus, $|{\cal X'} \cap S(a)| = N + 2M = k$ (rule $5$). \\
Since $\cal X'$ contains either a variable or it negation, for each pair of variables $(x, y) \in V(X) \cap U,\ d(x, y) = r$ (rule $3$). Further, in the satisfying assignment for $\Psi$ each clause $C_j = x \vee y \vee z$, has at least one of the variables set to $1$. So, for each pair of nodes $(p, q) \in V(X) \cap C, \ d(p, q) = r$ ({\sc Claim ~\ref{claim:minDiaClaim2} } and rule $3$) . Therefore, distance between any two nodes in $\cal X'$ is $r$ (rule $4$).\\
Thus, if $\Psi$ has a satisfying assignment then $G$ has a subgraph $\cal X'$ with $|{\cal X'} \cap S(a)| = k$ and $diameter({\cal X'}) = r$. 
\end{proof}
\begin{claim}
\label{claim:minDiaClaim4} Let  $k =  N + 2M$. If $G$ has a sub-graph $\cal X'$ with $|{\cal X'} \cap S(a)| \ge k$ and $diameter({\cal X'}) \le r$ then $\Psi$ has a satisfying assignment.
\end{claim}
\begin{proof}
If $diameter({\cal X'}) \le r$ then it contains either $u$ or $\neg u$ but not both because $d(u, \neg u) > r$ ({\sc Claim ~\ref{claim:minDiaClaim1}}). Since $k = N + 2M$, for each variable $u \in U$, $\cal X'$ contains a node corresponding to either $u$ or $\neg u$ (not both) and for each clause $C_j \in C$, $\cal X'$ contains nodes corresponding to $C_{j1}$ and $C_{j2}$ (rule $5$). Now, since $diameter({\cal X'}) \le r$, it implies that $d(C_{j1}, C_{j2}) \le r$. This implies that at least one of the nodes corresponding to $x, y, z$ in $C_j$ is included in the sub-graph $\cal X'$ ({\sc Claim ~\ref{claim:minDiaClaim2}}). Now, if each variable $u \in U \cap V({\cal X'})$ is set to $1$, then $\Psi$ has a satisfying assignment.
\end{proof}
{\sc Claims ~\ref{claim:minDiaClaim3}} and ~\ref{claim:minDiaClaim4} prove that {\it Diameter-sTF} is NP-hard. Since {\it Diameter-sTF} is the special case of {\it Diameter-mTF}, its NP-hardness proof follows.
\end{proof}

\section{Min Diameter Approximation}
\label{sec:minDia2Approx}
\begin{proof} [of Theorem~\ref{thm:diamapprox}]
The analysis we present here is similar to the analysis of the {\it RarestFirst} algorithm presented in ~\cite{LLT}. First, consider the solution $\cal X'$ output by the {\it MinDiameter} algorithm, and let $a_{rare} \in T$ be the skill possessed by the least number of individuals in $\cal X$. Also, let $i^*$ be the individual picked from set $S(a_{rare})$ to be included in the solution $\cal X'$. Now, consider two other skills $a_1 \ne a_2 \ne a_{rare}$ and individuals $i, i' \in \cal X$ such that $i \in S(a_1), i \not \in S(a_2)$ and $i' \not \in S(a_1), i' \in S(a_2)$. If $i, i'$ are part of the team reported by the {\it MinDiameter} algorithm, it means that $d(i^*, i) \le d_k(i^*, S(a_1), k_1)$ and $d(i^*, i') \le d_k(i^*, S(a_2), k_2)$. Due to the way the algorithm operates, we can lower bound the Cc-R cost of the optimal solution, $\cal X^*$,  as follows: 

\begin{equation}\label{DiaBounds}
d(i^*, i) \le \mbox{Cc-R}({\cal X^*}) \mbox{ and }  d(i^*, i') \le \mbox{Cc-R}({\cal X^*})
\end{equation}
Since we have assumed that the distance function $d$ satisfies the triangle inequality, \\
$d (i, i') \le d(i, i^*) + d(i^*, i')$\\
By applying the bounds given in ~\eqref{DiaBounds}, we get the proposed approximation factor. \\
$d (i, i') \le$ Cc-R($\cal X^*) +$ Cc-R(${\cal X^*}) \le 2 \cdot $Cc-R($\cal X^*$).
\end{proof}

\section{Experimental Setup}
\label{sec:expSetup}
We use a snapshot of the DBLP data downloaded on May 17, 2010 to create a benchmark data set for our experiments. We only consider the papers published in the domains of Database (DB), Data Mining (DM), Artificial Intelligence (AI) and Theory (T) conferences. We select papers from a total of $21$ conferences categorized as follows: $DB = \{\textsc{sigmod, vldb, icde, icdt, edbt,}$\\
$\textsc{pods}\}$, $DM = \{\textsc{www, kdd, sdm, pkdd, icdm}\}$, $AI =$ \{\textsc{icml, ecml,colt, uai}\}, and $T = \{\textsc{soda, focs, stoc, stacs, icalp,}$\\
$\textsc{esa}\}$.
%We refer to the set of selected papers as the DBLP dataset. 
%We now proceed to generate the input to the Team Formation Problem as follows.
We define the skill set $\cal T = \{\textsc{t, ai, db, dm}\}$. The set of skilled individuals $X_{dblp}$ consists of the set of authors with at least three papers in these domains. Two authors $i_1, i_2$ are connected in the graph $G_{dblp} (X_{dblp}, E)$ if they appear as co-authors in at least two papers in DBLP. The above procedure creates a set $X_{dblp}$ consisting of $6137$ individuals. The maximum component size is $3869$. We use this for all the experiments. The skill set $X_i$ of each such author $i$ is defined as $X_i = \{ t \mid t \in {\cal T} \ and \ P_i(t) \ne \phi \}$ where $P_i(t)$ denotes the set of papers coauthored by $i$ that are published in the conferences in the domain $t$. 
%Further, each edge $e(i_1, i_2)$ is assigned an edge depending on the number of publications co-authored by $i_1$ and $i_2$.

%{\it Maximum Density Team Formation.} To evaluate the algorithms {\it s-DensestAlk} and {\it m-DensestAlk}, for each edge $e(i_1, i_2)$, we set the edge weight $w(i_1, i_2) = |P_{i1} \cap P_{i2}|$, where $P_{i1}$ and $P_{i2}$ represent the set of papers published by $i_1$ and $i_2$
{\it Maximum Density Team Formation.} To evaluate the algorithms ~\ref{algo:sDlk} and ~\ref{algo:mDlk}, for each edge $e(i_1, i_2)$, we set the edge weight $w(i_1, i_2) = |P_{i1} \cap P_{i2}|$, where $P_{i1}$ and $P_{i2}$ represent the set of papers published by $i_1$ and $i_2$ respectively. For the subgraph, say $G'(V', E')$ returned by these algorithms, we calculate the density, $d' = \frac{W(G')}{|V(G')|}$. 
% I COMMENTED THE BELOW. I GUESS ITS OK NOT TO TALK ABOUT THIS? - Atish
%Note that a different edge weight could also be chosen, such as $\frac{|P_{i1} \cap P_{i2}}{|P_{i1} \cup P_{i2}}|$. However, we wanted to associate higher weight with edges corresponding to {\em heavy} nodes. 
%Therefore we chose $|P_{i1} \cap P_{i2}|$.
%; as shown later, this does give us qualitatively good results.

{\it Minimum Diameter Team Formation.} Here, we set edge-weight $w(i_1, i_2) = 1 - \frac{|P_{i1} \cap P_{i2} |}{| P_{i1} \cup P_{i2} |}$ as suggested in the paper~\cite{LLT}.  For comparison, when a subgraph $G'(V', E')$ is returned by the {\it MinDiameter}, we compute its density by considering the induced subgraph on vertices $V''$, say $G''$ (which could contain more edges that $E'$). The density calculated is $d'' = \frac{W(G'')}{|V(G'')|}$ with edge weights $w(i_1, i_2) =  |P_{i1} \cap P_{i2}|$. 

%It is to be expected that {\it MinDiameter} performs worse in terms of density as the algorithm is designed to optimize a different objective. However, we believe that density is a better suited objective for collaborative compatibility. Further, the %goal of this section is to show that our density-based algorithms perform well independently. We therefore perform evaluations based on the objective as well as qualitatively. We now present the heuristic algorithms that build on algorithms {\it s-%DensestAlk} and {\it m-DensestAlk}.

\section{Heuristic Algorithm Pseudocodes}
\label{sec:heuristicAlgos}
\begin{algorithm}[]
\caption{EnhancedDense($G, T$)}
\label{algo:edDlk}
\begin{algorithmic}[1]
\STATE $G' \leftarrow$  {\it s-DensestAlk(G, T)}
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G', T)$
\STATE Return $\arg \min_{C'_i \in {\cal C'}} | C'_i |$ 
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[]
\caption{EnhanceComponent($G', T$)}
\label{algo:ecDlk} 
\begin{algorithmic}[1]
\STATE (Note: $T= \{<a, k>\}$)
\FOR {each component $C_i \in G'$}
\STATE $C'_i \leftarrow C_i$, $Ni \leftarrow N(C_i) - C_i$ 
\STATE (note: $N(C_i)$ denotes neighbors of nodes in $C_i$)
\FOR {each node $v \in N_i$}
\IF { $| V(C'_i) \cap S(a) | \ge k$}
\STATE ${\cal C'} \leftarrow {\cal C'} \cup C'_i$
\STATE break for loop
\ENDIF
\IF {$v \in S(a)$}
\STATE $C'_i \leftarrow C'_i \cup v $
\ENDIF
\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[]
\caption{PartialTrimmedDense($G, T$)}
\label{algo:ptDlk}
\begin{algorithmic}[1]
\STATE (Note: $T = \{<a, k>\}$)
\STATE $G' \leftarrow$  {\it s-DensestAlk(G, T)}
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G',T)$
\FOR {each component $C'_i \in {\cal C'}$}
\STATE $Q \leftarrow \{ u \mid u \in C'_i \mbox { and } u \not \in S(a) \}$
\WHILE {$Q$ not empty and $| V(C'_i) - S(a) | > k$}
\STATE $u_{min} \leftarrow$ pop lowest degree node from $Q$
\IF {($C'_i - u_{min}$) is connected}
\STATE $C'_i \leftarrow C'_i - u_{min}$
\ENDIF
\ENDWHILE
\IF {$| V(C'_i) - S(a) | > k$}
\STATE ${\cal C'} \leftarrow {\cal C'} - C'_i$
\ENDIF
\ENDFOR 
\STATE Return $\arg \max_{C'_i \in {\cal C'}} density(C'_i)$ 
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[]
\caption{CompleteTrimmedDense($G,T$)} 
\label{algo:ctDlk}
\begin{algorithmic}[1]
\STATE (Note: T $= \{<a, k>\}$)
\STATE $G' \leftarrow$  {\it s-DensestAlk(G,T)}
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G', T)$
\FOR {each component $C'_i \in {\cal C'}$}
\STATE $Q \leftarrow V(C_i) - S(a)$
\WHILE {$Q$ is not empty}
\STATE $u_{min} \leftarrow$ pop lowest degree node from $Q$
\IF {($C'_i - u_{min}$) is connected}
\STATE $C'_i \leftarrow C'_i - u_{min}$
\ENDIF
\ENDWHILE
\ENDFOR 
\STATE Return $\arg \min_{C'_i \in {\cal C'}} | V(C'_i) |$
\end{algorithmic}
\end{algorithm}
\balance
\end{appendix}